class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    /*
    如果右括号大于括号数一定构成不了有效括号
    如果左括号==n,说明左括号已经用完
    如果右括号小于等于左括号，说明可以继续添加右括号
    当左括号数和右括号数==n,说明已经找到一个有效的括号串
    */
    string str="";
    vector<string>ans;
    void helper(int n,int left,int right,string str,vector<string>&ans)
    {
        if(right>left) return;
        if(right==n&&left==n) 
        {
            ans.push_back(str);return;
        }
        if(left<n)
        {
            helper(n, left+1, right, str+="(", ans);
            str.pop_back();
        }
        if(right<left)
        {
            helper(n, left, right+1, str+=")", ans);
            str.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        // write code here
        helper(n, 0, 0, str, ans);
        return ans;
    }
};